package a3_p04_jw_kw.spanningtree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.Pseudograph;

import a1_p04_jw_kw.graph.GraphCreater;
import a1_p04_jw_kw.graph.GraphUtility;
import a1_p04_jw_kw.struct.GraphSetup;
import a1_p04_jw_kw.struct.GraphStatistic;
import a1_p04_jw_kw.struct.GraphTransition;
import a1_p04_jw_kw.struct.Node;
import a3_p04_jw_kw.comparator.EdgeComparator;
import a3_p04_jw_kw.comparator.NodeComparator;

public class Kruska {
	Graph<Node,DefaultWeightedEdge> g;
	Pseudograph<Node,DefaultWeightedEdge> spanningTree;
	PriorityQueue<DefaultWeightedEdge> l;
	
	ArrayList<DefaultWeightedEdge> newEdges;
	
	HashMap<Node,Node> parents;
	HashMap<Node,ArrayList<Node>> neighbors;
	HashMap<Node,Double> distance;	
	
	HashMap<Node,Node> domains = new HashMap<Node,Node>();
	
	GraphStatistic stats = new GraphStatistic();
	
	long clock;	
	
	final private static Double INFINITE = 99999999.0;
	
	public Kruska(Graph<Node,DefaultWeightedEdge> g) {
		this.g = g;
		
	}
	
	public void createSpanningTree() {
		startWatch();
		
		//initialize
		Set<DefaultWeightedEdge> edgeSet = g.edgeSet();
		spanningTree = new Pseudograph<Node,DefaultWeightedEdge>(DefaultWeightedEdge.class);
		
		LinkedList<DefaultWeightedEdge> edges = new LinkedList<DefaultWeightedEdge>(edgeSet);
		Collections.sort(edges, new EdgeComparator(g));
		
		for (Node n : g.vertexSet()) {
			domains.put(n, n);
			
		}
		
		
		for (int i = 0; i < edges.size(); i ++) {
			DefaultWeightedEdge edge = edges.get(i);
			
			if (!buildsCircle(edge)) {
				
				
				spanningTree.addVertex(g.getEdgeSource(edge));
				spanningTree.addVertex(g.getEdgeTarget(edge));
				
				spanningTree.addEdge(g.getEdgeSource(edge), g.getEdgeTarget(edge));
				spanningTree.setEdgeWeight((spanningTree.getEdge(g.getEdgeSource(edge), g.getEdgeTarget(edge))), g.getEdgeWeight(edge));
				
			}
			
			
		}
		
		stopWatch();
	}
	
	//returns the sum of all edge weights
	public double getEdgeWeightSum() {
		double sum = 0.0;
		for (DefaultWeightedEdge e : this.spanningTree.edgeSet()) {
			sum = sum + this.spanningTree.getEdgeWeight(e);
			
		}
		
		
		return sum;
	}
	
	public Graph<Node,DefaultWeightedEdge> getSpanningTree() {
		return this.spanningTree;
		
	}
	
	
	//returns true if the give edge will create a circle
	public boolean buildsCircle(DefaultWeightedEdge e) {
		//union join, see 
		Node sourceDomain = domains.get(g.getEdgeSource(e));
		Node targetDomain = domains.get(g.getEdgeTarget(e));
			
		if (sourceDomain.equals(targetDomain)) {
			return true;
			
		} else {
			for (Node n : g.vertexSet()) {
				if (domains.get(n).equals(targetDomain)) {
					domains.put(n, sourceDomain);
					
				}
				
			}
			
			return false;
		}
		
	}
	
	public GraphStatistic getStatistic() {
		return this.stats;
		
	}	
	
	private void startWatch() {
		this.clock = System.currentTimeMillis();
		
	}
	
	private void stopWatch() {
		long stop = System.currentTimeMillis();
		stats.time = stats.time + (stop - clock);
		
	}	

}
